#include <cstdio>

long long pow( int p, int n )
{
    long long ret = 1;
    int i;
    for ( i = 0; i < n; i++ ) ret *= p;
    return ret;
}

int gcd( int a, int b )
{
    int rem;
    while ( b )
    {
        rem = a % b;
        a = b;
        b = rem;
    }
    return a;
}

int main( )
{
    int n, i;
    long long ans;
    while ( scanf("%d", &n) && n != -1 )
    {
        if ( n == 0 )
        {
            puts("0");
            continue;
        }
        ans = 0;
        for ( i = 0; i < n; i++ )
            ans += pow( 3, gcd( n, i ) );
        if ( n & 1 )
            ans += n * pow( 3, n / 2 + 1 );
        else
            ans += n / 2 * pow( 3, n / 2 + 1 ) + n / 2 * pow( 3, n / 2 );
        ans /= n * 2;
        printf("%I64d\n", ans);
    }
    return 0;
}
